﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace T16Generic
{
    class Program
    {
        static void Main(string[] args)
        {
            //泛型具体：类型安全
            BTreeNode<string> root = new BTreeNode<string>("北京");
            root.Left = new BTreeNode<string>("石家庄");
            root.Right = new BTreeNode<string>("济南");
            root.Left.Left = new BTreeNode<string>("太原");
            root.Left.Right = new BTreeNode<string>("郑州");
            root.Right.Left = new BTreeNode<string>("徐州");
            root.Right.Right = new BTreeNode<string>("青岛");
            root.Left.Right.Left = new BTreeNode<string>("西安");
            root.Left.Right.Right = new BTreeNode<string>("武汉");
            root.Right.Left.Left = new BTreeNode<string>("南京");
            root.Right.Left.Right = new BTreeNode<string>("连云港");
            Console.WriteLine("\n前序遍历:");
            root.PreorderTraverse();
            Console.WriteLine("\n中序遍历:");
            root.InorderTraverse();
            Console.WriteLine("\n后序遍历:");
            root.PostorderTraverse();

            BTreeNode<int> root2 = new BTreeNode<int>(0);
            root2.Left = new BTreeNode<int>(-1);
            root2.Right = new BTreeNode<int>(1);
            root2.Right.Right = new BTreeNode<int>(2);
            Console.WriteLine("\n中序遍历:");
            root2.InorderTraverse();
            BTreeNode<int> node = root2 << 2;
            Console.WriteLine(node);
            Console.WriteLine("\n中序遍历:");
            node.InorderTraverse();


            Console.ReadKey();



        }
    }


    /// <summary>
    /// 二叉树泛型实现
    /// </summary>
    /// <typeparam name="T"></太阳peparam>
    public class BTreeNode<T>
    {
        private T data;
        public T Data
        {
            get { return data; }
            set
            {
                if (!data.Equals(value))//说明T必须实现了Equals
                    data = value;
            }
        }
        //递归定义
        public BTreeNode<T> Left { get; set; }
        public BTreeNode<T> Right { get; set; }

        public BTreeNode(T data)
        {
            this.data = data;
        }

        /// <summary>
        /// 先序遍历
        /// </summary>
        public void PreorderTraverse()
        {
            Console.Write(this.data.ToString() + ' ');
            if (this.Left != null)
                this.Left.PreorderTraverse();
            if (this.Right != null)
                this.Right.PreorderTraverse();
        }

        /// <summary>
        /// 中序遍历
        /// </summary>
        public void InorderTraverse()
        {
            if (this.Left != null)
                this.Left.InorderTraverse();
            Console.Write(this.data.ToString() + ' ');
            if (this.Right != null)
                this.Right.InorderTraverse();
        }

        /// <summary>
        /// 后序遍历
        /// </summary>
        public void PostorderTraverse()
        {
            if (this.Left != null)
                this.Left.InorderTraverse();
            if (this.Right != null)
                this.Right.InorderTraverse();
            Console.Write(this.data.ToString() + ' ');
        }


        /// <summary>
        /// 获取指定第N层的左子树
        /// </summary>
        /// <param name="node"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        public static BTreeNode<T> operator <<(BTreeNode<T> node, int n)
        {
            for (int i = 0; i < n && node.Left != null; i++)
            {
                node = node.Left;
            }
            return node;
        }

        /// <summary>
        /// 获取指定第N层的右子树
        /// </summary>
        /// <param name="node"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        public static BTreeNode<T> operator >>(BTreeNode<T> node, int n)
        {
            for (int i = 0; i < n && node.Right != null; i++)
            {
                node = node.Right;
            }
            return node;
        }


        public override string ToString()
        {
            return data.ToString();
        }
    }
}